//
// Created by 86131 on 2023/11/14.
//

#include "../堆/ArrayList1.h"
template<typename T>
class MinHeap {
private:
    ArrayList1<T> heap;

    int parent(int index) {
        return (index - 1) / 2;
    }

    int leftChild(int index) {
        return 2 * index + 1;
    }

    int rightChild(int index) {
        return 2 * index + 2;
    }

    void swap(int& a, int& b) {
        int temp = a;
        a = b;
        b = temp;
    }

    void siftUp(int index) {
        while (index > 0 && heap.get(index) < heap.get(parent(index))){
            swap(heap.get(index), heap.get(parent(index)));
            index = parent(index);
        }
    }

    void siftDown(int index) {
        int maxIndex = index;
        int leftIndex = leftChild(index);
        int rightIndex = rightChild(index);

        if (leftIndex < heap.getSize() && heap.get(leftIndex) < heap.get(maxIndex)) {
            maxIndex = leftIndex;
        }

        if (rightIndex < heap.getSize() && heap.get(rightIndex) < heap.get(maxIndex)) {
            maxIndex = rightIndex;
        }

        if (index != maxIndex) {
            swap(heap.get(index), heap.get(maxIndex));
            siftDown(maxIndex);
        }
    }

public:
    void insert(int value) {
        heap.add(value);
        siftUp(heap.getSize() - 1);
    }

    int extractMin() {
        if (heap.empty()) {
            return -1; // or any other appropriate handling for an empty heap
        }

        int max = heap.get(0);
        swap(heap.get(0), heap.get(heap.getSize() - 1));
        heap.remove(heap.getSize()-1);
        siftDown(0);
        return max;
    }
    int getMax(){
        return heap.get(0);
    }
    int getsize(){
        return heap.getSize();
    }

};

